package com.example.demo.leetcode.classics150;

import java.util.Arrays;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _150最大正方形
 * @description
 * @date 2023/08/29 16:00
 * <p>
 * ******************************************************
 */
public class _150最大正方形 {
    public int maximalSquare1(char[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i < m; i++) {
            dp[i][1] = matrix[i][0] - '0';
        }
        for (int j = 1; j < n; j++) {
            dp[1][j] = matrix[0][j] - '0';
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (matrix[i - 1][j - 1] == '0') {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                } else {
                    dp[i][j] = Math.max(Math.max(dp[i - 1][j], dp[i][j - 1]), getMax(matrix, i - 1, j - 1));
                }
            }
        }


        return dp[m][n];
    }

    private int getMax(char[][] matrix, int i, int j) {
        int res = 1;
        int p = i;
        int q = j;
        while (p >= 0 && q >= 0) {
            if (matrix[p][q] == '1') {
                for (int x = p; x <= i; x++) {
                    for (int y = q; y <= j; y++) {
                        if (matrix[x][y] == '0') {
                            return res;
                        }
                    }
                }
                res = (i - p + 1) * (j - q + 1);

                p--;
                q--;
            } else {
                break;
            }
        }
        return res;
    }


    public int maximalSquare2(char[][] matrix) {
        int n = matrix.length;
        if (n == 0) return 0;
        int m = matrix[0].length;
        if (m == 0) return 0;
        int[][] dp = new int[n][m];
        int result = 0;
        //初始化base case
        for (int i = 0; i < n; i++) {
            dp[i][0] = matrix[i][0] - '0';
            result = Math.max(dp[i][0], result);
        }
        for (int i = 0; i < m; i++) {
            dp[0][i] = matrix[0][i] - '0';
            result = Math.max(dp[0][i], result);
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                //计算dp[i][j];
                if (matrix[i][j] == '1') {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) + 1;
                    result = Math.max(dp[i][j], result);
                }

            }
        }
        return result * result;

    }


    public int maximalSquare(char[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        // dp(i, j) 是以 matrix(i - 1, j - 1) 为 右下角 的正方形的最大边长
        // 以i - 1, j - 1为正方形的右下角的顶点的最大边长
        // 若某格子值为 1，则以此为右下角的正方形的；
        // 最大边长为：上面的正方形dp(i, j-1)、左面的正方形dp(i-1, j)或左上的正方形dp(i-1, j-1)中，最小的那个，再加上此格。
        int[][] dp = new int[m + 1][n + 1];
        int result = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (matrix[i - 1][j - 1] == '1') {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
                    result = Math.max(result, dp[i][j]);
                }
            }
        }
        return result * result;

    }

    public static void main(String[] args) {
        _150最大正方形 s = new _150最大正方形();
        System.out.println(s.maximalSquare(new char[][]{{'1', '0', '1', '0', '0'}, {'1', '0', '1', '1', '1'}, {'1', '1', '1', '1', '1'}, {'1', '0', '0', '1', '0'}}));
    }
}
